/*
 * Copyright (c) 2007, 2015, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
/*
 * Copyright 1999-2002,2004,2005 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.sun.org.apache.xerces.internal.dom;

import java.util.ArrayList;

import org.w3c.dom.DOMImplementation;
import org.w3c.dom.Element;
import org.w3c.dom.Node;

/**
 * The Document interface represents the entire HTML or XML document.
 * Conceptually, it is the root of the document tree, and provides the
 * primary access to the document's data.
 * <P>
 * Since elements, text nodes, comments, processing instructions,
 * etc. cannot exist outside the context of a Document, the Document
 * interface also contains the factory methods needed to create these
 * objects. The Node objects created have a ownerDocument attribute
 * which associates them with the Document within whose context they
 * were created.
 *
 * @version $Id: DeferredDocumentImpl.java,v 1.11 2010-11-01 04:39:38 joehw Exp $
 * @xerces.internal
 * @since PR-DOM-Level-1-19980818.
 */
public class DeferredDocumentImpl
    extends DocumentImpl
    implements DeferredNode {

  //
  // Constants
  //

  /**
   * Serialization version.
   */
  static final long serialVersionUID = 5186323580749626857L;

  // debugging

  /**
   * To include code for printing the ref count tables.
   */
  private static final boolean DEBUG_PRINT_REF_COUNTS = false;

  /**
   * To include code for printing the internal tables.
   */
  private static final boolean DEBUG_PRINT_TABLES = false;

  /**
   * To debug identifiers set to true and recompile.
   */
  private static final boolean DEBUG_IDS = false;

  // protected

  /**
   * Chunk shift.
   */
  protected static final int CHUNK_SHIFT = 8;           // 2^8 = 256

  /**
   * Chunk size.
   */
  protected static final int CHUNK_SIZE = (1 << CHUNK_SHIFT);

  /**
   * Chunk mask.
   */
  protected static final int CHUNK_MASK = CHUNK_SIZE - 1;

  /**
   * Initial chunk size.
   */
  protected static final int INITIAL_CHUNK_COUNT = (1 << (13 - CHUNK_SHIFT));   // 32

  //
  // Data
  //

  // lazy-eval information
  // To maximize memory consumption the actual semantic of these fields vary
  // depending on the node type.

  /**
   * Node count.
   */
  protected transient int fNodeCount = 0;

  /**
   * Node types.
   */
  protected transient int fNodeType[][];

  /**
   * Node names.
   */
  protected transient Object fNodeName[][];

  /**
   * Node values.
   */
  protected transient Object fNodeValue[][];

  /**
   * Node parents.
   */
  protected transient int fNodeParent[][];

  /**
   * Node first children.
   */
  protected transient int fNodeLastChild[][];

  /**
   * Node prev siblings.
   */
  protected transient int fNodePrevSib[][];

  /**
   * Node namespace URI.
   */
  protected transient Object fNodeURI[][];

  /**
   * Extra data.
   */
  protected transient int fNodeExtra[][];

  /**
   * Identifier count.
   */
  protected transient int fIdCount;

  /**
   * Identifier name indexes.
   */
  protected transient String fIdName[];

  /**
   * Identifier element indexes.
   */
  protected transient int fIdElement[];

  /**
   * DOM2: For namespace support in the deferred case.
   */
  // Implementation Note: The deferred element and attribute must know how to
  // interpret the int representing the qname.
  protected boolean fNamespacesEnabled = false;

  //
  // private data
  //
  private transient final StringBuilder fBufferStr = new StringBuilder();
  private transient final ArrayList fStrChunks = new ArrayList();

  //
  // Constructors
  //

  /**
   * NON-DOM: Actually creating a Document is outside the DOM's spec,
   * since it has to operate in terms of a particular implementation.
   */
  public DeferredDocumentImpl() {
    this(false);
  } // <init>()

  /**
   * NON-DOM: Actually creating a Document is outside the DOM's spec,
   * since it has to operate in terms of a particular implementation.
   */
  public DeferredDocumentImpl(boolean namespacesEnabled) {
    this(namespacesEnabled, false);
  } // <init>(boolean)

  /**
   * Experimental constructor.
   */
  public DeferredDocumentImpl(boolean namespaces, boolean grammarAccess) {
    super(grammarAccess);

    needsSyncData(true);
    needsSyncChildren(true);

    fNamespacesEnabled = namespaces;

  } // <init>(boolean,boolean)

  //
  // Public methods
  //

  /**
   * Retrieve information describing the abilities of this particular
   * DOM implementation. Intended to support applications that may be
   * using DOMs retrieved from several different sources, potentially
   * with different underlying representations.
   */
  public DOMImplementation getImplementation() {
    // Currently implemented as a singleton, since it's hardcoded
    // information anyway.
    return DeferredDOMImplementationImpl.getDOMImplementation();
  }

  /**
   * Returns the cached parser.getNamespaces() value.
   */
  boolean getNamespacesEnabled() {
    return fNamespacesEnabled;
  }

  void setNamespacesEnabled(boolean enable) {
    fNamespacesEnabled = enable;
  }

  // internal factory methods

  /**
   * Creates a document node in the table.
   */
  public int createDeferredDocument() {
    int nodeIndex = createNode(Node.DOCUMENT_NODE);
    return nodeIndex;
  }

  /**
   * Creates a doctype.
   */
  public int createDeferredDocumentType(String rootElementName,
      String publicId, String systemId) {

    // create node
    int nodeIndex = createNode(Node.DOCUMENT_TYPE_NODE);
    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;

    // save name, public id, system id
    setChunkValue(fNodeName, rootElementName, chunk, index);
    setChunkValue(fNodeValue, publicId, chunk, index);
    setChunkValue(fNodeURI, systemId, chunk, index);

    // return node index
    return nodeIndex;

  } // createDeferredDocumentType(String,String,String):int

  public void setInternalSubset(int doctypeIndex, String subset) {
    int chunk = doctypeIndex >> CHUNK_SHIFT;
    int index = doctypeIndex & CHUNK_MASK;

    // create extra data node to store internal subset
    int extraDataIndex = createNode(Node.DOCUMENT_TYPE_NODE);
    int echunk = extraDataIndex >> CHUNK_SHIFT;
    int eindex = extraDataIndex & CHUNK_MASK;
    setChunkIndex(fNodeExtra, extraDataIndex, chunk, index);
    setChunkValue(fNodeValue, subset, echunk, eindex);
  }

  /**
   * Creates a notation in the table.
   */
  public int createDeferredNotation(String notationName,
      String publicId, String systemId, String baseURI) {

    // create node
    int nodeIndex = createNode(Node.NOTATION_NODE);
    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;

    // create extra data node
    int extraDataIndex = createNode(Node.NOTATION_NODE);
    int echunk = extraDataIndex >> CHUNK_SHIFT;
    int eindex = extraDataIndex & CHUNK_MASK;

    // save name, public id, system id, and notation name
    setChunkValue(fNodeName, notationName, chunk, index);
    setChunkValue(fNodeValue, publicId, chunk, index);
    setChunkValue(fNodeURI, systemId, chunk, index);

    // in extra data node set baseURI value
    setChunkIndex(fNodeExtra, extraDataIndex, chunk, index);
    setChunkValue(fNodeName, baseURI, echunk, eindex);

    // return node index
    return nodeIndex;

  } // createDeferredNotation(String,String,String):int

  /**
   * Creates an entity in the table.
   */
  public int createDeferredEntity(String entityName, String publicId,
      String systemId, String notationName,
      String baseURI) {
    // create node
    int nodeIndex = createNode(Node.ENTITY_NODE);
    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;

    // create extra data node
    int extraDataIndex = createNode(Node.ENTITY_NODE);
    int echunk = extraDataIndex >> CHUNK_SHIFT;
    int eindex = extraDataIndex & CHUNK_MASK;

    // save name, public id, system id, and notation name
    setChunkValue(fNodeName, entityName, chunk, index);
    setChunkValue(fNodeValue, publicId, chunk, index);
    setChunkValue(fNodeURI, systemId, chunk, index);
    setChunkIndex(fNodeExtra, extraDataIndex, chunk, index);
    // set other values in the extra chunk
    // notation
    setChunkValue(fNodeName, notationName, echunk, eindex);
    // version  L3
    setChunkValue(fNodeValue, null, echunk, eindex);
    // encoding L3
    setChunkValue(fNodeURI, null, echunk, eindex);

    int extraDataIndex2 = createNode(Node.ENTITY_NODE);
    int echunk2 = extraDataIndex2 >> CHUNK_SHIFT;
    int eindex2 = extraDataIndex2 & CHUNK_MASK;

    setChunkIndex(fNodeExtra, extraDataIndex2, echunk, eindex);

    // baseURI
    setChunkValue(fNodeName, baseURI, echunk2, eindex2);

    // return node index
    return nodeIndex;

  } // createDeferredEntity(String,String,String,String):int

  public String getDeferredEntityBaseURI(int entityIndex) {
    if (entityIndex != -1) {
      int extraDataIndex = getNodeExtra(entityIndex, false);
      extraDataIndex = getNodeExtra(extraDataIndex, false);
      return getNodeName(extraDataIndex, false);
    }
    return null;
  }

  // DOM Level 3: setting encoding and version
  public void setEntityInfo(int currentEntityDecl,
      String version, String encoding) {
    int eNodeIndex = getNodeExtra(currentEntityDecl, false);
    if (eNodeIndex != -1) {
      int echunk = eNodeIndex >> CHUNK_SHIFT;
      int eindex = eNodeIndex & CHUNK_MASK;
      setChunkValue(fNodeValue, version, echunk, eindex);
      setChunkValue(fNodeURI, encoding, echunk, eindex);
    }
  }

  // DOM Level 3: sets element TypeInfo
  public void setTypeInfo(int elementNodeIndex, Object type) {
    int elementChunk = elementNodeIndex >> CHUNK_SHIFT;
    int elementIndex = elementNodeIndex & CHUNK_MASK;
    setChunkValue(fNodeValue, type, elementChunk, elementIndex);
  }

  /**
   * DOM Internal
   *
   * An attribute specifying the actual encoding of this document. This is
   * <code>null</code> otherwise.
   * <br> This attribute represents the property [character encoding scheme]
   * defined in .
   */
  public void setInputEncoding(int currentEntityDecl, String value) {
    // get first extra data chunk
    int nodeIndex = getNodeExtra(currentEntityDecl, false);
    // get second extra data chunk
    int extraDataIndex = getNodeExtra(nodeIndex, false);

    int echunk = extraDataIndex >> CHUNK_SHIFT;
    int eindex = extraDataIndex & CHUNK_MASK;

    setChunkValue(fNodeValue, value, echunk, eindex);

  }

  /**
   * Creates an entity reference node in the table.
   */
  public int createDeferredEntityReference(String name, String baseURI) {

    // create node
    int nodeIndex = createNode(Node.ENTITY_REFERENCE_NODE);
    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    setChunkValue(fNodeName, name, chunk, index);
    setChunkValue(fNodeValue, baseURI, chunk, index);

    // return node index
    return nodeIndex;

  } // createDeferredEntityReference(String):int


  /**
   * Creates an element node with a URI in the table and type information.
   *
   * @deprecated
   */
  public int createDeferredElement(String elementURI, String elementName,
      Object type) {

    // create node
    int elementNodeIndex = createNode(Node.ELEMENT_NODE);
    int elementChunk = elementNodeIndex >> CHUNK_SHIFT;
    int elementIndex = elementNodeIndex & CHUNK_MASK;
    setChunkValue(fNodeName, elementName, elementChunk, elementIndex);
    setChunkValue(fNodeURI, elementURI, elementChunk, elementIndex);
    setChunkValue(fNodeValue, type, elementChunk, elementIndex);

    // return node index
    return elementNodeIndex;

  } // createDeferredElement(String,String,Object):int

  /**
   * Creates an element node in the table.
   *
   * @deprecated
   */
  public int createDeferredElement(String elementName) {
    return createDeferredElement(null, elementName);
  }

  /**
   * Creates an element node with a URI in the table.
   */
  public int createDeferredElement(String elementURI, String elementName) {

    // create node
    int elementNodeIndex = createNode(Node.ELEMENT_NODE);
    int elementChunk = elementNodeIndex >> CHUNK_SHIFT;
    int elementIndex = elementNodeIndex & CHUNK_MASK;
    setChunkValue(fNodeName, elementName, elementChunk, elementIndex);
    setChunkValue(fNodeURI, elementURI, elementChunk, elementIndex);

    // return node index
    return elementNodeIndex;

  } // createDeferredElement(String,String):int


  /**
   * This method is used by the DOMParser to create attributes.
   *
   * @return int
   */
  public int setDeferredAttribute(int elementNodeIndex,
      String attrName,
      String attrURI,
      String attrValue,
      boolean specified,
      boolean id,
      Object type) {

    // create attribute
    int attrNodeIndex = createDeferredAttribute(attrName, attrURI, attrValue, specified);
    int attrChunk = attrNodeIndex >> CHUNK_SHIFT;
    int attrIndex = attrNodeIndex & CHUNK_MASK;
    // set attribute's parent to element
    setChunkIndex(fNodeParent, elementNodeIndex, attrChunk, attrIndex);

    int elementChunk = elementNodeIndex >> CHUNK_SHIFT;
    int elementIndex = elementNodeIndex & CHUNK_MASK;

    // get element's last attribute
    int lastAttrNodeIndex = getChunkIndex(fNodeExtra, elementChunk, elementIndex);
    if (lastAttrNodeIndex != 0) {
      // add link from new attribute to last attribute
      setChunkIndex(fNodePrevSib, lastAttrNodeIndex, attrChunk, attrIndex);
    }
    // add link from element to new last attribute
    setChunkIndex(fNodeExtra, attrNodeIndex, elementChunk, elementIndex);

    int extra = getChunkIndex(fNodeExtra, attrChunk, attrIndex);
    if (id) {
      extra = extra | ID;
      setChunkIndex(fNodeExtra, extra, attrChunk, attrIndex);
      String value = getChunkValue(fNodeValue, attrChunk, attrIndex);
      putIdentifier(value, elementNodeIndex);
    }
    // store type information
    if (type != null) {
      int extraDataIndex = createNode(DeferredNode.TYPE_NODE);
      int echunk = extraDataIndex >> CHUNK_SHIFT;
      int eindex = extraDataIndex & CHUNK_MASK;

      setChunkIndex(fNodeLastChild, extraDataIndex, attrChunk, attrIndex);
      setChunkValue(fNodeValue, type, echunk, eindex);
    }

    // return node index
    return attrNodeIndex;
  }

  /**
   * Sets an attribute on an element node.
   *
   * @deprecated
   */
  public int setDeferredAttribute(int elementNodeIndex,
      String attrName, String attrURI,
      String attrValue, boolean specified) {
    // create attribute
    int attrNodeIndex = createDeferredAttribute(attrName, attrURI,
        attrValue, specified);
    int attrChunk = attrNodeIndex >> CHUNK_SHIFT;
    int attrIndex = attrNodeIndex & CHUNK_MASK;
    // set attribute's parent to element
    setChunkIndex(fNodeParent, elementNodeIndex, attrChunk, attrIndex);

    int elementChunk = elementNodeIndex >> CHUNK_SHIFT;
    int elementIndex = elementNodeIndex & CHUNK_MASK;

    // get element's last attribute
    int lastAttrNodeIndex = getChunkIndex(fNodeExtra,
        elementChunk, elementIndex);
    if (lastAttrNodeIndex != 0) {
      // add link from new attribute to last attribute
      setChunkIndex(fNodePrevSib, lastAttrNodeIndex,
          attrChunk, attrIndex);
    }
    // add link from element to new last attribute
    setChunkIndex(fNodeExtra, attrNodeIndex,
        elementChunk, elementIndex);

    // return node index
    return attrNodeIndex;

  } // setDeferredAttribute(int,String,String,String,boolean):int

  /**
   * Creates an attribute in the table.
   */
  public int createDeferredAttribute(String attrName, String attrValue,
      boolean specified) {
    return createDeferredAttribute(attrName, null, attrValue, specified);
  }

  /**
   * Creates an attribute with a URI in the table.
   */
  public int createDeferredAttribute(String attrName, String attrURI,
      String attrValue, boolean specified) {

    // create node
    int nodeIndex = createNode(NodeImpl.ATTRIBUTE_NODE);
    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    setChunkValue(fNodeName, attrName, chunk, index);
    setChunkValue(fNodeURI, attrURI, chunk, index);
    setChunkValue(fNodeValue, attrValue, chunk, index);
    int extra = specified ? SPECIFIED : 0;
    setChunkIndex(fNodeExtra, extra, chunk, index);

    // return node index
    return nodeIndex;

  } // createDeferredAttribute(String,String,String,boolean):int

  /**
   * Creates an element definition in the table.
   */
  public int createDeferredElementDefinition(String elementName) {

    // create node
    int nodeIndex = createNode(NodeImpl.ELEMENT_DEFINITION_NODE);
    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    setChunkValue(fNodeName, elementName, chunk, index);

    // return node index
    return nodeIndex;

  } // createDeferredElementDefinition(String):int

  /**
   * Creates a text node in the table.
   */
  public int createDeferredTextNode(String data,
      boolean ignorableWhitespace) {

    // create node
    int nodeIndex = createNode(Node.TEXT_NODE);
    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    setChunkValue(fNodeValue, data, chunk, index);
    // use extra to store ignorableWhitespace info
    setChunkIndex(fNodeExtra, ignorableWhitespace ? 1 : 0, chunk, index);

    // return node index
    return nodeIndex;

  } // createDeferredTextNode(String,boolean):int

  /**
   * Creates a CDATA section node in the table.
   */
  public int createDeferredCDATASection(String data) {

    // create node
    int nodeIndex = createNode(Node.CDATA_SECTION_NODE);
    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    setChunkValue(fNodeValue, data, chunk, index);

    // return node index
    return nodeIndex;

  } // createDeferredCDATASection(String):int

  /**
   * Creates a processing instruction node in the table.
   */
  public int createDeferredProcessingInstruction(String target,
      String data) {
    // create node
    int nodeIndex = createNode(Node.PROCESSING_INSTRUCTION_NODE);
    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    setChunkValue(fNodeName, target, chunk, index);
    setChunkValue(fNodeValue, data, chunk, index);
    // return node index
    return nodeIndex;

  } // createDeferredProcessingInstruction(String,String):int

  /**
   * Creates a comment node in the table.
   */
  public int createDeferredComment(String data) {

    // create node
    int nodeIndex = createNode(Node.COMMENT_NODE);
    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    setChunkValue(fNodeValue, data, chunk, index);

    // return node index
    return nodeIndex;

  } // createDeferredComment(String):int

  /**
   * Creates a clone of the specified node.
   */
  public int cloneNode(int nodeIndex, boolean deep) {

    // clone immediate node

    int nchunk = nodeIndex >> CHUNK_SHIFT;
    int nindex = nodeIndex & CHUNK_MASK;
    int nodeType = fNodeType[nchunk][nindex];
    int cloneIndex = createNode((short) nodeType);
    int cchunk = cloneIndex >> CHUNK_SHIFT;
    int cindex = cloneIndex & CHUNK_MASK;
    setChunkValue(fNodeName, fNodeName[nchunk][nindex], cchunk, cindex);
    setChunkValue(fNodeValue, fNodeValue[nchunk][nindex], cchunk, cindex);
    setChunkValue(fNodeURI, fNodeURI[nchunk][nindex], cchunk, cindex);
    int extraIndex = fNodeExtra[nchunk][nindex];
    if (extraIndex != -1) {
      if (nodeType != Node.ATTRIBUTE_NODE && nodeType != Node.TEXT_NODE) {
        extraIndex = cloneNode(extraIndex, false);
      }
      setChunkIndex(fNodeExtra, extraIndex, cchunk, cindex);
    }

    // clone and attach children
    if (deep) {
      int prevIndex = -1;
      int childIndex = getLastChild(nodeIndex, false);
      while (childIndex != -1) {
        int clonedChildIndex = cloneNode(childIndex, deep);
        insertBefore(cloneIndex, clonedChildIndex, prevIndex);
        prevIndex = clonedChildIndex;
        childIndex = getRealPrevSibling(childIndex, false);
      }


    }

    // return cloned node index
    return cloneIndex;

  } // cloneNode(int,boolean):int

  /**
   * Appends a child to the specified parent in the table.
   */
  public void appendChild(int parentIndex, int childIndex) {

    // append parent index
    int pchunk = parentIndex >> CHUNK_SHIFT;
    int pindex = parentIndex & CHUNK_MASK;
    int cchunk = childIndex >> CHUNK_SHIFT;
    int cindex = childIndex & CHUNK_MASK;
    setChunkIndex(fNodeParent, parentIndex, cchunk, cindex);

    // set previous sibling of new child
    int olast = getChunkIndex(fNodeLastChild, pchunk, pindex);
    setChunkIndex(fNodePrevSib, olast, cchunk, cindex);

    // update parent's last child
    setChunkIndex(fNodeLastChild, childIndex, pchunk, pindex);

  } // appendChild(int,int)

  /**
   * Adds an attribute node to the specified element.
   */
  public int setAttributeNode(int elemIndex, int attrIndex) {

    int echunk = elemIndex >> CHUNK_SHIFT;
    int eindex = elemIndex & CHUNK_MASK;
    int achunk = attrIndex >> CHUNK_SHIFT;
    int aindex = attrIndex & CHUNK_MASK;

    // see if this attribute is already here
    String attrName = getChunkValue(fNodeName, achunk, aindex);
    int oldAttrIndex = getChunkIndex(fNodeExtra, echunk, eindex);
    int nextIndex = -1;
    int oachunk = -1;
    int oaindex = -1;
    while (oldAttrIndex != -1) {
      oachunk = oldAttrIndex >> CHUNK_SHIFT;
      oaindex = oldAttrIndex & CHUNK_MASK;
      String oldAttrName = getChunkValue(fNodeName, oachunk, oaindex);
      if (oldAttrName.equals(attrName)) {
        break;
      }
      nextIndex = oldAttrIndex;
      oldAttrIndex = getChunkIndex(fNodePrevSib, oachunk, oaindex);
    }

    // remove old attribute
    if (oldAttrIndex != -1) {

      // patch links
      int prevIndex = getChunkIndex(fNodePrevSib, oachunk, oaindex);
      if (nextIndex == -1) {
        setChunkIndex(fNodeExtra, prevIndex, echunk, eindex);
      } else {
        int pchunk = nextIndex >> CHUNK_SHIFT;
        int pindex = nextIndex & CHUNK_MASK;
        setChunkIndex(fNodePrevSib, prevIndex, pchunk, pindex);
      }

      // remove connections to siblings
      clearChunkIndex(fNodeType, oachunk, oaindex);
      clearChunkValue(fNodeName, oachunk, oaindex);
      clearChunkValue(fNodeValue, oachunk, oaindex);
      clearChunkIndex(fNodeParent, oachunk, oaindex);
      clearChunkIndex(fNodePrevSib, oachunk, oaindex);
      int attrTextIndex =
          clearChunkIndex(fNodeLastChild, oachunk, oaindex);
      int atchunk = attrTextIndex >> CHUNK_SHIFT;
      int atindex = attrTextIndex & CHUNK_MASK;
      clearChunkIndex(fNodeType, atchunk, atindex);
      clearChunkValue(fNodeValue, atchunk, atindex);
      clearChunkIndex(fNodeParent, atchunk, atindex);
      clearChunkIndex(fNodeLastChild, atchunk, atindex);
    }

    // add new attribute
    int prevIndex = getChunkIndex(fNodeExtra, echunk, eindex);
    setChunkIndex(fNodeExtra, attrIndex, echunk, eindex);
    setChunkIndex(fNodePrevSib, prevIndex, achunk, aindex);

    // return
    return oldAttrIndex;

  } // setAttributeNode(int,int):int


  /**
   * Adds an attribute node to the specified element.
   */
  public void setIdAttributeNode(int elemIndex, int attrIndex) {

    int chunk = attrIndex >> CHUNK_SHIFT;
    int index = attrIndex & CHUNK_MASK;
    int extra = getChunkIndex(fNodeExtra, chunk, index);
    extra = extra | ID;
    setChunkIndex(fNodeExtra, extra, chunk, index);

    String value = getChunkValue(fNodeValue, chunk, index);
    putIdentifier(value, elemIndex);
  }


  /**
   * Sets type of attribute
   */
  public void setIdAttribute(int attrIndex) {

    int chunk = attrIndex >> CHUNK_SHIFT;
    int index = attrIndex & CHUNK_MASK;
    int extra = getChunkIndex(fNodeExtra, chunk, index);
    extra = extra | ID;
    setChunkIndex(fNodeExtra, extra, chunk, index);
  }

  /**
   * Inserts a child before the specified node in the table.
   */
  public int insertBefore(int parentIndex, int newChildIndex, int refChildIndex) {

    if (refChildIndex == -1) {
      appendChild(parentIndex, newChildIndex);
      return newChildIndex;
    }

    int nchunk = newChildIndex >> CHUNK_SHIFT;
    int nindex = newChildIndex & CHUNK_MASK;
    int rchunk = refChildIndex >> CHUNK_SHIFT;
    int rindex = refChildIndex & CHUNK_MASK;
    int previousIndex = getChunkIndex(fNodePrevSib, rchunk, rindex);
    setChunkIndex(fNodePrevSib, newChildIndex, rchunk, rindex);
    setChunkIndex(fNodePrevSib, previousIndex, nchunk, nindex);

    return newChildIndex;

  } // insertBefore(int,int,int):int

  /**
   * Sets the last child of the parentIndex to childIndex.
   */
  public void setAsLastChild(int parentIndex, int childIndex) {
    int pchunk = parentIndex >> CHUNK_SHIFT;
    int pindex = parentIndex & CHUNK_MASK;
    setChunkIndex(fNodeLastChild, childIndex, pchunk, pindex);
  } // setAsLastChild(int,int)

  /**
   * Returns the parent node of the given node.
   * <em>Calling this method does not free the parent index.</em>
   */
  public int getParentNode(int nodeIndex) {
    return getParentNode(nodeIndex, false);
  }

  /**
   * Returns the parent node of the given node.
   *
   * @param free True to free parent node.
   */
  public int getParentNode(int nodeIndex, boolean free) {

    if (nodeIndex == -1) {
      return -1;
    }

    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    return free ? clearChunkIndex(fNodeParent, chunk, index)
        : getChunkIndex(fNodeParent, chunk, index);

  } // getParentNode(int):int

  /**
   * Returns the last child of the given node.
   */
  public int getLastChild(int nodeIndex) {
    return getLastChild(nodeIndex, true);
  }

  /**
   * Returns the last child of the given node.
   *
   * @param free True to free child index.
   */
  public int getLastChild(int nodeIndex, boolean free) {

    if (nodeIndex == -1) {
      return -1;
    }

    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    return free ? clearChunkIndex(fNodeLastChild, chunk, index)
        : getChunkIndex(fNodeLastChild, chunk, index);

  } // getLastChild(int,boolean):int

  /**
   * Returns the prev sibling of the given node.
   * This is post-normalization of Text Nodes.
   */
  public int getPrevSibling(int nodeIndex) {
    return getPrevSibling(nodeIndex, true);
  }

  /**
   * Returns the prev sibling of the given node.
   *
   * @param free True to free sibling index.
   */
  public int getPrevSibling(int nodeIndex, boolean free) {

    if (nodeIndex == -1) {
      return -1;
    }

    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    int type = getChunkIndex(fNodeType, chunk, index);
    if (type == Node.TEXT_NODE) {
      do {
        nodeIndex = getChunkIndex(fNodePrevSib, chunk, index);
        if (nodeIndex == -1) {
          break;
        }
        chunk = nodeIndex >> CHUNK_SHIFT;
        index = nodeIndex & CHUNK_MASK;
        type = getChunkIndex(fNodeType, chunk, index);
      } while (type == Node.TEXT_NODE);
    } else {
      nodeIndex = getChunkIndex(fNodePrevSib, chunk, index);
    }

    return nodeIndex;

  } // getPrevSibling(int,boolean):int

  /**
   * Returns the <i>real</i> prev sibling of the given node,
   * directly from the data structures. Used by TextImpl#getNodeValue()
   * to normalize values.
   */
  public int getRealPrevSibling(int nodeIndex) {
    return getRealPrevSibling(nodeIndex, true);
  }

  /**
   * Returns the <i>real</i> prev sibling of the given node.
   *
   * @param free True to free sibling index.
   */
  public int getRealPrevSibling(int nodeIndex, boolean free) {

    if (nodeIndex == -1) {
      return -1;
    }

    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    return free ? clearChunkIndex(fNodePrevSib, chunk, index)
        : getChunkIndex(fNodePrevSib, chunk, index);

  } // getReadPrevSibling(int,boolean):int

  /**
   * Returns the index of the element definition in the table
   * with the specified name index, or -1 if no such definition
   * exists.
   */
  public int lookupElementDefinition(String elementName) {

    if (fNodeCount > 1) {

      // find doctype
      int docTypeIndex = -1;
      int nchunk = 0;
      int nindex = 0;
      for (int index = getChunkIndex(fNodeLastChild, nchunk, nindex);
          index != -1;
          index = getChunkIndex(fNodePrevSib, nchunk, nindex)) {

        nchunk = index >> CHUNK_SHIFT;
        nindex = index & CHUNK_MASK;
        if (getChunkIndex(fNodeType, nchunk, nindex) == Node.DOCUMENT_TYPE_NODE) {
          docTypeIndex = index;
          break;
        }
      }

      // find element definition
      if (docTypeIndex == -1) {
        return -1;
      }
      nchunk = docTypeIndex >> CHUNK_SHIFT;
      nindex = docTypeIndex & CHUNK_MASK;
      for (int index = getChunkIndex(fNodeLastChild, nchunk, nindex);
          index != -1;
          index = getChunkIndex(fNodePrevSib, nchunk, nindex)) {

        nchunk = index >> CHUNK_SHIFT;
        nindex = index & CHUNK_MASK;
        if (getChunkIndex(fNodeType, nchunk, nindex) ==
            NodeImpl.ELEMENT_DEFINITION_NODE
            && getChunkValue(fNodeName, nchunk, nindex) == elementName) {
          return index;
        }
      }
    }

    return -1;

  } // lookupElementDefinition(String):int

  /**
   * Instantiates the requested node object.
   */
  public DeferredNode getNodeObject(int nodeIndex) {

    // is there anything to do?
    if (nodeIndex == -1) {
      return null;
    }

    // get node type
    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    int type = getChunkIndex(fNodeType, chunk, index);
    if (type != Node.TEXT_NODE && type != Node.CDATA_SECTION_NODE) {
      clearChunkIndex(fNodeType, chunk, index);
    }

    // create new node
    DeferredNode node = null;
    switch (type) {

      //
      // Standard DOM node types
      //

      case Node.ATTRIBUTE_NODE: {
        if (fNamespacesEnabled) {
          node = new DeferredAttrNSImpl(this, nodeIndex);
        } else {
          node = new DeferredAttrImpl(this, nodeIndex);
        }
        break;
      }

      case Node.CDATA_SECTION_NODE: {
        node = new DeferredCDATASectionImpl(this, nodeIndex);
        break;
      }

      case Node.COMMENT_NODE: {
        node = new DeferredCommentImpl(this, nodeIndex);
        break;
      }

      // NOTE: Document fragments can never be "fast".
      //
      //       The parser will never ask to create a document
      //       fragment during the parse. Document fragments
      //       are used by the application *after* the parse.
      //
      // case Node.DOCUMENT_FRAGMENT_NODE: { break; }
      case Node.DOCUMENT_NODE: {
        // this node is never "fast"
        node = this;
        break;
      }

      case Node.DOCUMENT_TYPE_NODE: {
        node = new DeferredDocumentTypeImpl(this, nodeIndex);
        // save the doctype node
        docType = (DocumentTypeImpl) node;
        break;
      }

      case Node.ELEMENT_NODE: {

        if (DEBUG_IDS) {
          System.out.println("getNodeObject(ELEMENT_NODE): " + nodeIndex);
        }

        // create node
        if (fNamespacesEnabled) {
          node = new DeferredElementNSImpl(this, nodeIndex);
        } else {
          node = new DeferredElementImpl(this, nodeIndex);
        }

        // check to see if this element needs to be
        // registered for its ID attributes
        if (fIdElement != null) {
          int idIndex = binarySearch(fIdElement, 0,
              fIdCount - 1, nodeIndex);
          while (idIndex != -1) {

            if (DEBUG_IDS) {
              System.out.println("  id index: " + idIndex);
              System.out.println("  fIdName[" + idIndex +
                  "]: " + fIdName[idIndex]);
            }

            // register ID
            String name = fIdName[idIndex];
            if (name != null) {
              if (DEBUG_IDS) {
                System.out.println("  name: " + name);
                System.out.print("getNodeObject()#");
              }
              putIdentifier0(name, (Element) node);
              fIdName[idIndex] = null;
            }

            // continue if there are more IDs for
            // this element
            if (idIndex + 1 < fIdCount &&
                fIdElement[idIndex + 1] == nodeIndex) {
              idIndex++;
            } else {
              idIndex = -1;
            }
          }
        }
        break;
      }

      case Node.ENTITY_NODE: {
        node = new DeferredEntityImpl(this, nodeIndex);
        break;
      }

      case Node.ENTITY_REFERENCE_NODE: {
        node = new DeferredEntityReferenceImpl(this, nodeIndex);
        break;
      }

      case Node.NOTATION_NODE: {
        node = new DeferredNotationImpl(this, nodeIndex);
        break;
      }

      case Node.PROCESSING_INSTRUCTION_NODE: {
        node = new DeferredProcessingInstructionImpl(this, nodeIndex);
        break;
      }

      case Node.TEXT_NODE: {
        node = new DeferredTextImpl(this, nodeIndex);
        break;
      }

      //
      // non-standard DOM node types
      //

      case NodeImpl.ELEMENT_DEFINITION_NODE: {
        node = new DeferredElementDefinitionImpl(this, nodeIndex);
        break;
      }

      default: {
        throw new IllegalArgumentException("type: " + type);
      }

    } // switch node type

    // store and return
    if (node != null) {
      return node;
    }

    // error
    throw new IllegalArgumentException();

  } // createNodeObject(int):Node

  /**
   * Returns the name of the given node.
   */
  public String getNodeName(int nodeIndex) {
    return getNodeName(nodeIndex, true);
  } // getNodeNameString(int):String

  /**
   * Returns the name of the given node.
   *
   * @param free True to free the string index.
   */
  public String getNodeName(int nodeIndex, boolean free) {

    if (nodeIndex == -1) {
      return null;
    }

    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    return free ? clearChunkValue(fNodeName, chunk, index)
        : getChunkValue(fNodeName, chunk, index);

  } // getNodeName(int,boolean):String

  /**
   * Returns the real value of the given node.
   */
  public String getNodeValueString(int nodeIndex) {
    return getNodeValueString(nodeIndex, true);
  } // getNodeValueString(int):String

  /**
   * Returns the real value of the given node.
   *
   * @param free True to free the string index.
   */
  public String getNodeValueString(int nodeIndex, boolean free) {

    if (nodeIndex == -1) {
      return null;
    }

    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    String value = free ? clearChunkValue(fNodeValue, chunk, index)
        : getChunkValue(fNodeValue, chunk, index);
    if (value == null) {
      return null;
    }

    int type = getChunkIndex(fNodeType, chunk, index);
    if (type == Node.TEXT_NODE) {
      int prevSib = getRealPrevSibling(nodeIndex);
      if (prevSib != -1 &&
          getNodeType(prevSib, false) == Node.TEXT_NODE) {
        // append data that is stored in fNodeValue
        // REVISIT: for text nodes it works differently than for CDATA
        //          nodes.
        fStrChunks.add(value);
        do {
          // go in reverse order: find last child, then
          // its previous sibling, etc
          chunk = prevSib >> CHUNK_SHIFT;
          index = prevSib & CHUNK_MASK;
          value = getChunkValue(fNodeValue, chunk, index);
          fStrChunks.add(value);
          prevSib = getChunkIndex(fNodePrevSib, chunk, index);
          if (prevSib == -1) {
            break;
          }
        } while (getNodeType(prevSib, false) == Node.TEXT_NODE);

        int chunkCount = fStrChunks.size();

        // add to the buffer in the correct order.
        for (int i = chunkCount - 1; i >= 0; i--) {
          fBufferStr.append((String) fStrChunks.get(i));
        }

        value = fBufferStr.toString();
        fStrChunks.clear();
        fBufferStr.setLength(0);
        return value;
      }
    } else if (type == Node.CDATA_SECTION_NODE) {
      // find if any other data stored in children
      int child = getLastChild(nodeIndex, false);
      if (child != -1) {
        // append data that is stored in fNodeValue
        fBufferStr.append(value);
        while (child != -1) {
          // go in reverse order: find last child, then
          // its previous sibling, etc
          chunk = child >> CHUNK_SHIFT;
          index = child & CHUNK_MASK;
          value = getChunkValue(fNodeValue, chunk, index);
          fStrChunks.add(value);
          child = getChunkIndex(fNodePrevSib, chunk, index);
        }
        // add to the buffer in the correct order.
        for (int i = fStrChunks.size() - 1; i >= 0; i--) {
          fBufferStr.append((String) fStrChunks.get(i));
        }

        value = fBufferStr.toString();
        fStrChunks.clear();
        fBufferStr.setLength(0);
        return value;
      }
    }

    return value;

  } // getNodeValueString(int,boolean):String

  /**
   * Returns the value of the given node.
   */
  public String getNodeValue(int nodeIndex) {
    return getNodeValue(nodeIndex, true);
  }

  /**
   * Clears the type info that is stored in the fNodeValue array
   *
   * @return Object - type information for the attribute/element node
   */
  public Object getTypeInfo(int nodeIndex) {
    if (nodeIndex == -1) {
      return null;
    }

    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;

    Object value = fNodeValue[chunk] != null ? fNodeValue[chunk][index] : null;
    if (value != null) {
      fNodeValue[chunk][index] = null;
      RefCount c = (RefCount) fNodeValue[chunk][CHUNK_SIZE];
      c.fCount--;
      if (c.fCount == 0) {
        fNodeValue[chunk] = null;
      }
    }
    return value;
  }

  /**
   * Returns the value of the given node.
   *
   * @param free True to free the value index.
   */
  public String getNodeValue(int nodeIndex, boolean free) {

    if (nodeIndex == -1) {
      return null;
    }

    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    return free ? clearChunkValue(fNodeValue, chunk, index)
        : getChunkValue(fNodeValue, chunk, index);

  } // getNodeValue(int,boolean):String

  /**
   * Returns the extra info of the given node.
   * Used by AttrImpl to store specified value (1 == true).
   */
  public int getNodeExtra(int nodeIndex) {
    return getNodeExtra(nodeIndex, true);
  }

  /**
   * Returns the extra info of the given node.
   *
   * @param free True to free the value index.
   */
  public int getNodeExtra(int nodeIndex, boolean free) {

    if (nodeIndex == -1) {
      return -1;
    }

    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    return free ? clearChunkIndex(fNodeExtra, chunk, index)
        : getChunkIndex(fNodeExtra, chunk, index);

  } // getNodeExtra(int,boolean):int

  /**
   * Returns the type of the given node.
   */
  public short getNodeType(int nodeIndex) {
    return getNodeType(nodeIndex, true);
  }

  /**
   * Returns the type of the given node.
   *
   * @param free True to free type index.
   */
  public short getNodeType(int nodeIndex, boolean free) {

    if (nodeIndex == -1) {
      return -1;
    }

    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    return free ? (short) clearChunkIndex(fNodeType, chunk, index)
        : (short) getChunkIndex(fNodeType, chunk, index);

  } // getNodeType(int):int

  /**
   * Returns the attribute value of the given name.
   */
  public String getAttribute(int elemIndex, String name) {
    if (elemIndex == -1 || name == null) {
      return null;
    }
    int echunk = elemIndex >> CHUNK_SHIFT;
    int eindex = elemIndex & CHUNK_MASK;
    int attrIndex = getChunkIndex(fNodeExtra, echunk, eindex);
    while (attrIndex != -1) {
      int achunk = attrIndex >> CHUNK_SHIFT;
      int aindex = attrIndex & CHUNK_MASK;
      if (getChunkValue(fNodeName, achunk, aindex) == name) {
        return getChunkValue(fNodeValue, achunk, aindex);
      }
      attrIndex = getChunkIndex(fNodePrevSib, achunk, aindex);
    }
    return null;
  }

  /**
   * Returns the URI of the given node.
   */
  public String getNodeURI(int nodeIndex) {
    return getNodeURI(nodeIndex, true);
  }

  /**
   * Returns the URI of the given node.
   *
   * @param free True to free URI index.
   */
  public String getNodeURI(int nodeIndex, boolean free) {

    if (nodeIndex == -1) {
      return null;
    }

    int chunk = nodeIndex >> CHUNK_SHIFT;
    int index = nodeIndex & CHUNK_MASK;
    return free ? clearChunkValue(fNodeURI, chunk, index)
        : getChunkValue(fNodeURI, chunk, index);

  } // getNodeURI(int,int):String

  // identifier maintenance

  /**
   * Registers an identifier name with a specified element node.
   */
  public void putIdentifier(String name, int elementNodeIndex) {

    if (DEBUG_IDS) {
      System.out.println("putIdentifier(" + name + ", "
          + elementNodeIndex + ')' + " // " +
          getChunkValue(fNodeName,
              elementNodeIndex >> CHUNK_SHIFT,
              elementNodeIndex & CHUNK_MASK));
    }

    // initialize arrays
    if (fIdName == null) {
      fIdName = new String[64];
      fIdElement = new int[64];
    }

    // resize arrays
    if (fIdCount == fIdName.length) {
      String idName[] = new String[fIdCount * 2];
      System.arraycopy(fIdName, 0, idName, 0, fIdCount);
      fIdName = idName;

      int idElement[] = new int[idName.length];
      System.arraycopy(fIdElement, 0, idElement, 0, fIdCount);
      fIdElement = idElement;
    }

    // store identifier
    fIdName[fIdCount] = name;
    fIdElement[fIdCount] = elementNodeIndex;
    fIdCount++;

  } // putIdentifier(String,int)

  //
  // DEBUG
  //

  /**
   * Prints out the tables.
   */
  public void print() {

    if (DEBUG_PRINT_REF_COUNTS) {
      System.out.print("num\t");
      System.out.print("type\t");
      System.out.print("name\t");
      System.out.print("val\t");
      System.out.print("par\t");
      System.out.print("lch\t");
      System.out.print("psib");
      System.out.println();
      for (int i = 0; i < fNodeType.length; i++) {
        if (fNodeType[i] != null) {
          // separator
          System.out.print("--------");
          System.out.print("--------");
          System.out.print("--------");
          System.out.print("--------");
          System.out.print("--------");
          System.out.print("--------");
          System.out.print("--------");
          System.out.println();

          // ref count
          System.out.print(i);
          System.out.print('\t');
          switch (fNodeType[i][CHUNK_SIZE]) {
            case DocumentImpl.ELEMENT_DEFINITION_NODE: {
              System.out.print("EDef");
              break;
            }
            case Node.DOCUMENT_NODE: {
              System.out.print("Doc");
              break;
            }
            case Node.DOCUMENT_TYPE_NODE: {
              System.out.print("DType");
              break;
            }
            case Node.COMMENT_NODE: {
              System.out.print("Com");
              break;
            }
            case Node.PROCESSING_INSTRUCTION_NODE: {
              System.out.print("PI");
              break;
            }
            case Node.ELEMENT_NODE: {
              System.out.print("Elem");
              break;
            }
            case Node.ENTITY_NODE: {
              System.out.print("Ent");
              break;
            }
            case Node.ENTITY_REFERENCE_NODE: {
              System.out.print("ERef");
              break;
            }
            case Node.TEXT_NODE: {
              System.out.print("Text");
              break;
            }
            case Node.ATTRIBUTE_NODE: {
              System.out.print("Attr");
              break;
            }
            case DeferredNode.TYPE_NODE: {
              System.out.print("TypeInfo");
              break;
            }
            default: {
              System.out.print("?" + fNodeType[i][CHUNK_SIZE]);
            }
          }
          System.out.print('\t');
          System.out.print(fNodeName[i][CHUNK_SIZE]);
          System.out.print('\t');
          System.out.print(fNodeValue[i][CHUNK_SIZE]);
          System.out.print('\t');
          System.out.print(fNodeURI[i][CHUNK_SIZE]);
          System.out.print('\t');
          System.out.print(fNodeParent[i][CHUNK_SIZE]);
          System.out.print('\t');
          System.out.print(fNodeLastChild[i][CHUNK_SIZE]);
          System.out.print('\t');
          System.out.print(fNodePrevSib[i][CHUNK_SIZE]);
          System.out.print('\t');
          System.out.print(fNodeExtra[i][CHUNK_SIZE]);
          System.out.println();
        }
      }
    }

    if (DEBUG_PRINT_TABLES) {
      // This assumes that the document is small
      System.out.println("# start table");
      for (int i = 0; i < fNodeCount; i++) {
        int chunk = i >> CHUNK_SHIFT;
        int index = i & CHUNK_MASK;
        if (i % 10 == 0) {
          System.out.print("num\t");
          System.out.print("type\t");
          System.out.print("name\t");
          System.out.print("val\t");
          System.out.print("uri\t");
          System.out.print("par\t");
          System.out.print("lch\t");
          System.out.print("psib\t");
          System.out.print("xtra");
          System.out.println();
        }
        System.out.print(i);
        System.out.print('\t');
        switch (getChunkIndex(fNodeType, chunk, index)) {
          case DocumentImpl.ELEMENT_DEFINITION_NODE: {
            System.out.print("EDef");
            break;
          }
          case Node.DOCUMENT_NODE: {
            System.out.print("Doc");
            break;
          }
          case Node.DOCUMENT_TYPE_NODE: {
            System.out.print("DType");
            break;
          }
          case Node.COMMENT_NODE: {
            System.out.print("Com");
            break;
          }
          case Node.PROCESSING_INSTRUCTION_NODE: {
            System.out.print("PI");
            break;
          }
          case Node.ELEMENT_NODE: {
            System.out.print("Elem");
            break;
          }
          case Node.ENTITY_NODE: {
            System.out.print("Ent");
            break;
          }
          case Node.ENTITY_REFERENCE_NODE: {
            System.out.print("ERef");
            break;
          }
          case Node.TEXT_NODE: {
            System.out.print("Text");
            break;
          }
          case Node.ATTRIBUTE_NODE: {
            System.out.print("Attr");
            break;
          }
          case DeferredNode.TYPE_NODE: {
            System.out.print("TypeInfo");
            break;
          }
          default: {
            System.out.print("?" + getChunkIndex(fNodeType, chunk, index));
          }
        }
        System.out.print('\t');
        System.out.print(getChunkValue(fNodeName, chunk, index));
        System.out.print('\t');
        System.out.print(getNodeValue(chunk, index));
        System.out.print('\t');
        System.out.print(getChunkValue(fNodeURI, chunk, index));
        System.out.print('\t');
        System.out.print(getChunkIndex(fNodeParent, chunk, index));
        System.out.print('\t');
        System.out.print(getChunkIndex(fNodeLastChild, chunk, index));
        System.out.print('\t');
        System.out.print(getChunkIndex(fNodePrevSib, chunk, index));
        System.out.print('\t');
        System.out.print(getChunkIndex(fNodeExtra, chunk, index));
        System.out.println();
      }
      System.out.println("# end table");
    }

  } // print()

  //
  // DeferredNode methods
  //

  /**
   * Returns the node index.
   */
  public int getNodeIndex() {
    return 0;
  }

  //
  // Protected methods
  //

  /**
   * Synchronizes the node's data.
   */
  protected void synchronizeData() {

    // no need to sync in the future
    needsSyncData(false);

    // fluff up enough nodes to fill identifiers hash
    if (fIdElement != null) {

      // REVISIT: There has to be a more efficient way of
      //          doing this. But keep in mind that the
      //          tree can have been altered and re-ordered
      //          before all of the element nodes with ID
      //          attributes have been registered. For now
      //          this is reasonable and safe. -Ac

      IntVector path = new IntVector();
      for (int i = 0; i < fIdCount; i++) {

        // ignore if it's already been registered
        int elementNodeIndex = fIdElement[i];
        String idName = fIdName[i];
        if (idName == null) {
          continue;
        }

        // find path from this element to the root
        path.removeAllElements();
        int index = elementNodeIndex;
        do {
          path.addElement(index);
          int pchunk = index >> CHUNK_SHIFT;
          int pindex = index & CHUNK_MASK;
          index = getChunkIndex(fNodeParent, pchunk, pindex);
        } while (index != -1);

        // Traverse path (backwards), fluffing the elements
        // along the way. When this loop finishes, "place"
        // will contain the reference to the element node
        // we're interested in. -Ac
        Node place = this;
        for (int j = path.size() - 2; j >= 0; j--) {
          index = path.elementAt(j);
          Node child = place.getLastChild();
          while (child != null) {
            if (child instanceof DeferredNode) {
              int nodeIndex =
                  ((DeferredNode) child).getNodeIndex();
              if (nodeIndex == index) {
                place = child;
                break;
              }
            }
            child = child.getPreviousSibling();
          }
        }

        // register the element
        Element element = (Element) place;
        putIdentifier0(idName, element);
        fIdName[i] = null;

        // see if there are more IDs on this element
        while (i + 1 < fIdCount &&
            fIdElement[i + 1] == elementNodeIndex) {
          idName = fIdName[++i];
          if (idName == null) {
            continue;
          }
          putIdentifier0(idName, element);
        }
      }

    } // if identifiers

  } // synchronizeData()

  /**
   * Synchronizes the node's children with the internal structure.
   * Fluffing the children at once solves a lot of work to keep
   * the two structures in sync. The problem gets worse when
   * editing the tree -- this makes it a lot easier.
   */
  protected void synchronizeChildren() {

    if (needsSyncData()) {
      synchronizeData();
            /*
             * when we have elements with IDs this method is being recursively
             * called from synchronizeData, in which case we've already gone
             * through the following and we can now simply stop here.
             */
      if (!needsSyncChildren()) {
        return;
      }
    }

    // we don't want to generate any event for this so turn them off
    boolean orig = mutationEvents;
    mutationEvents = false;

    // no need to sync in the future
    needsSyncChildren(false);

    getNodeType(0);

    // create children and link them as siblings
    ChildNode first = null;
    ChildNode last = null;
    for (int index = getLastChild(0);
        index != -1;
        index = getPrevSibling(index)) {

      ChildNode node = (ChildNode) getNodeObject(index);
      if (last == null) {
        last = node;
      } else {
        first.previousSibling = node;
      }
      node.ownerNode = this;
      node.isOwned(true);
      node.nextSibling = first;
      first = node;

      // save doctype and document type
      int type = node.getNodeType();
      if (type == Node.ELEMENT_NODE) {
        docElement = (ElementImpl) node;
      } else if (type == Node.DOCUMENT_TYPE_NODE) {
        docType = (DocumentTypeImpl) node;
      }
    }

    if (first != null) {
      firstChild = first;
      first.isFirstChild(true);
      lastChild(last);
    }

    // set mutation events flag back to its original value
    mutationEvents = orig;

  } // synchronizeChildren()

  /**
   * Synchronizes the node's children with the internal structure.
   * Fluffing the children at once solves a lot of work to keep
   * the two structures in sync. The problem gets worse when
   * editing the tree -- this makes it a lot easier.
   * This is not directly used in this class but this method is
   * here so that it can be shared by all deferred subclasses of AttrImpl.
   */
  protected final void synchronizeChildren(AttrImpl a, int nodeIndex) {

    // we don't want to generate any event for this so turn them off
    boolean orig = getMutationEvents();
    setMutationEvents(false);

    // no need to sync in the future
    a.needsSyncChildren(false);

    // create children and link them as siblings or simply store the value
    // as a String if all we have is one piece of text
    int last = getLastChild(nodeIndex);
    int prev = getPrevSibling(last);
    if (prev == -1) {
      a.value = getNodeValueString(nodeIndex);
      a.hasStringValue(true);
    } else {
      ChildNode firstNode = null;
      ChildNode lastNode = null;
      for (int index = last; index != -1;
          index = getPrevSibling(index)) {

        ChildNode node = (ChildNode) getNodeObject(index);
        if (lastNode == null) {
          lastNode = node;
        } else {
          firstNode.previousSibling = node;
        }
        node.ownerNode = a;
        node.isOwned(true);
        node.nextSibling = firstNode;
        firstNode = node;
      }
      if (lastNode != null) {
        a.value = firstNode; // firstChild = firstNode
        firstNode.isFirstChild(true);
        a.lastChild(lastNode);
      }
      a.hasStringValue(false);
    }

    // set mutation events flag back to its original value
    setMutationEvents(orig);

  } // synchronizeChildren(AttrImpl,int):void


  /**
   * Synchronizes the node's children with the internal structure.
   * Fluffing the children at once solves a lot of work to keep
   * the two structures in sync. The problem gets worse when
   * editing the tree -- this makes it a lot easier.
   * This is not directly used in this class but this method is
   * here so that it can be shared by all deferred subclasses of ParentNode.
   */
  protected final void synchronizeChildren(ParentNode p, int nodeIndex) {

    // we don't want to generate any event for this so turn them off
    boolean orig = getMutationEvents();
    setMutationEvents(false);

    // no need to sync in the future
    p.needsSyncChildren(false);

    // create children and link them as siblings
    ChildNode firstNode = null;
    ChildNode lastNode = null;
    for (int index = getLastChild(nodeIndex);
        index != -1;
        index = getPrevSibling(index)) {

      ChildNode node = (ChildNode) getNodeObject(index);
      if (lastNode == null) {
        lastNode = node;
      } else {
        firstNode.previousSibling = node;
      }
      node.ownerNode = p;
      node.isOwned(true);
      node.nextSibling = firstNode;
      firstNode = node;
    }
    if (lastNode != null) {
      p.firstChild = firstNode;
      firstNode.isFirstChild(true);
      p.lastChild(lastNode);
    }

    // set mutation events flag back to its original value
    setMutationEvents(orig);

  } // synchronizeChildren(ParentNode,int):void

  // utility methods

  /**
   * Ensures that the internal tables are large enough.
   */
  protected void ensureCapacity(int chunk) {
    if (fNodeType == null) {
      // create buffers
      fNodeType = new int[INITIAL_CHUNK_COUNT][];
      fNodeName = new Object[INITIAL_CHUNK_COUNT][];
      fNodeValue = new Object[INITIAL_CHUNK_COUNT][];
      fNodeParent = new int[INITIAL_CHUNK_COUNT][];
      fNodeLastChild = new int[INITIAL_CHUNK_COUNT][];
      fNodePrevSib = new int[INITIAL_CHUNK_COUNT][];
      fNodeURI = new Object[INITIAL_CHUNK_COUNT][];
      fNodeExtra = new int[INITIAL_CHUNK_COUNT][];
    } else if (fNodeType.length <= chunk) {
      // resize the tables
      int newsize = chunk * 2;

      int[][] newArray = new int[newsize][];
      System.arraycopy(fNodeType, 0, newArray, 0, chunk);
      fNodeType = newArray;

      Object[][] newStrArray = new Object[newsize][];
      System.arraycopy(fNodeName, 0, newStrArray, 0, chunk);
      fNodeName = newStrArray;

      newStrArray = new Object[newsize][];
      System.arraycopy(fNodeValue, 0, newStrArray, 0, chunk);
      fNodeValue = newStrArray;

      newArray = new int[newsize][];
      System.arraycopy(fNodeParent, 0, newArray, 0, chunk);
      fNodeParent = newArray;

      newArray = new int[newsize][];
      System.arraycopy(fNodeLastChild, 0, newArray, 0, chunk);
      fNodeLastChild = newArray;

      newArray = new int[newsize][];
      System.arraycopy(fNodePrevSib, 0, newArray, 0, chunk);
      fNodePrevSib = newArray;

      newStrArray = new Object[newsize][];
      System.arraycopy(fNodeURI, 0, newStrArray, 0, chunk);
      fNodeURI = newStrArray;

      newArray = new int[newsize][];
      System.arraycopy(fNodeExtra, 0, newArray, 0, chunk);
      fNodeExtra = newArray;
    } else if (fNodeType[chunk] != null) {
      // Done - there's sufficient capacity
      return;
    }

    // create new chunks
    createChunk(fNodeType, chunk);
    createChunk(fNodeName, chunk);
    createChunk(fNodeValue, chunk);
    createChunk(fNodeParent, chunk);
    createChunk(fNodeLastChild, chunk);
    createChunk(fNodePrevSib, chunk);
    createChunk(fNodeURI, chunk);
    createChunk(fNodeExtra, chunk);

    // Done
    return;

  } // ensureCapacity(int,int)

  /**
   * Creates a node of the specified type.
   */
  protected int createNode(short nodeType) {
    // ensure tables are large enough
    int chunk = fNodeCount >> CHUNK_SHIFT;
    int index = fNodeCount & CHUNK_MASK;
    ensureCapacity(chunk);

    // initialize node
    setChunkIndex(fNodeType, nodeType, chunk, index);

    // return node index number
    return fNodeCount++;

  } // createNode(short):int

  /**
   * Performs a binary search for a target value in an array of
   * values. The array of values must be in ascending sorted order
   * before calling this method and all array values must be
   * non-negative.
   *
   * @param values The array of values to search.
   * @param start The starting offset of the search.
   * @param end The ending offset of the search.
   * @param target The target value.
   * @return This function will return the <i>first</i> occurrence of the target value, or -1 if the
   * target value cannot be found.
   */
  protected static int binarySearch(final int values[],
      int start, int end, int target) {

    if (DEBUG_IDS) {
      System.out.println("binarySearch(), target: " + target);
    }

    // look for target value
    while (start <= end) {

      // is this the one we're looking for?
      int middle = (start + end) >>> 1;
      int value = values[middle];
      if (DEBUG_IDS) {
        System.out.print("  value: " + value + ", target: " + target + " // ");
        print(values, start, end, middle, target);
      }
      if (value == target) {
        while (middle > 0 && values[middle - 1] == target) {
          middle--;
        }
        if (DEBUG_IDS) {
          System.out.println("FOUND AT " + middle);
        }
        return middle;
      }

      // is this point higher or lower?
      if (value > target) {
        end = middle - 1;
      } else {
        start = middle + 1;
      }

    } // while

    // not found
    if (DEBUG_IDS) {
      System.out.println("NOT FOUND!");
    }
    return -1;

  } // binarySearch(int[],int,int,int):int

  //
  // Private methods
  //
  private static final int[] INIT_ARRAY = new int[CHUNK_SIZE + 1];

  static {
    for (int i = 0; i < CHUNK_SIZE; i++) {
      INIT_ARRAY[i] = -1;
    }
  }

  /**
   * Creates the specified chunk in the given array of chunks.
   */
  private final void createChunk(int data[][], int chunk) {
    data[chunk] = new int[CHUNK_SIZE + 1];
    System.arraycopy(INIT_ARRAY, 0, data[chunk], 0, CHUNK_SIZE);
  }

  static final class RefCount {

    int fCount;
  }

  private final void createChunk(Object data[][], int chunk) {
    data[chunk] = new Object[CHUNK_SIZE + 1];
    data[chunk][CHUNK_SIZE] = new RefCount();
  }

  /**
   * Sets the specified value in the given of data at the chunk and index.
   *
   * @return Returns the old value.
   */
  private final int setChunkIndex(int data[][], int value,
      int chunk, int index) {
    if (value == -1) {
      return clearChunkIndex(data, chunk, index);
    }
    int[] dataChunk = data[chunk];
    // Re-create chunk if it was deleted.
    if (dataChunk == null) {
      createChunk(data, chunk);
      dataChunk = data[chunk];
    }
    int ovalue = dataChunk[index];
    if (ovalue == -1) {
      dataChunk[CHUNK_SIZE]++;
    }
    dataChunk[index] = value;
    return ovalue;
  }

  private final String setChunkValue(Object data[][], Object value,
      int chunk, int index) {
    if (value == null) {
      return clearChunkValue(data, chunk, index);
    }
    Object[] dataChunk = data[chunk];
    // Re-create chunk if it was deleted.
    if (dataChunk == null) {
      createChunk(data, chunk);
      dataChunk = data[chunk];
    }
    String ovalue = (String) dataChunk[index];
    if (ovalue == null) {
      RefCount c = (RefCount) dataChunk[CHUNK_SIZE];
      c.fCount++;
    }
    dataChunk[index] = value;
    return ovalue;
  }

  /**
   * Returns the specified value in the given data at the chunk and index.
   */
  private final int getChunkIndex(int data[][], int chunk, int index) {
    return data[chunk] != null ? data[chunk][index] : -1;
  }

  private final String getChunkValue(Object data[][], int chunk, int index) {
    return data[chunk] != null ? (String) data[chunk][index] : null;
  }

  private final String getNodeValue(int chunk, int index) {
    Object data = fNodeValue[chunk][index];
    if (data == null) {
      return null;
    } else if (data instanceof String) {
      return (String) data;
    } else {
      // type information
      return data.toString();
    }
  }


  /**
   * Clears the specified value in the given data at the chunk and index.
   * Note that this method will clear the given chunk if the reference
   * count becomes zero.
   *
   * @return Returns the old value.
   */
  private final int clearChunkIndex(int data[][], int chunk, int index) {
    int value = data[chunk] != null ? data[chunk][index] : -1;
    if (value != -1) {
      data[chunk][CHUNK_SIZE]--;
      data[chunk][index] = -1;
      if (data[chunk][CHUNK_SIZE] == 0) {
        data[chunk] = null;
      }
    }
    return value;
  }

  private final String clearChunkValue(Object data[][],
      int chunk, int index) {
    String value = data[chunk] != null ? (String) data[chunk][index] : null;
    if (value != null) {
      data[chunk][index] = null;
      RefCount c = (RefCount) data[chunk][CHUNK_SIZE];
      c.fCount--;
      if (c.fCount == 0) {
        data[chunk] = null;
      }
    }
    return value;
  }

  /**
   * This version of putIdentifier is needed to avoid fluffing
   * all of the paths to ID attributes when a node object is
   * created that contains an ID attribute.
   */
  private final void putIdentifier0(String idName, Element element) {

    if (DEBUG_IDS) {
      System.out.println("putIdentifier0(" +
          idName + ", " +
          element + ')');
    }

    // create hashtable
    if (identifiers == null) {
      identifiers = new java.util.Hashtable();
    }

    // save ID and its associated element
    identifiers.put(idName, element);

  } // putIdentifier0(String,Element)

  /**
   * Prints the ID array.
   */
  private static void print(int values[], int start, int end,
      int middle, int target) {

    if (DEBUG_IDS) {
      System.out.print(start);
      System.out.print(" [");
      for (int i = start; i < end; i++) {
        if (middle == i) {
          System.out.print("!");
        }
        System.out.print(values[i]);
        if (values[i] == target) {
          System.out.print("*");
        }
        if (i < end - 1) {
          System.out.print(" ");
        }
      }
      System.out.println("] " + end);
    }

  } // print(int[],int,int,int,int)

  //
  // Classes
  //

  /**
   * A simple integer vector.
   */
  static final class IntVector {

    //
    // Data
    //

    /**
     * Data.
     */
    private int data[];

    /**
     * Size.
     */
    private int size;

    //
    // Public methods
    //

    /**
     * Returns the length of this vector.
     */
    public int size() {
      return size;
    }

    /**
     * Returns the element at the specified index.
     */
    public int elementAt(int index) {
      return data[index];
    }

    /**
     * Appends an element to the end of the vector.
     */
    public void addElement(int element) {
      ensureCapacity(size + 1);
      data[size++] = element;
    }

    /**
     * Clears the vector.
     */
    public void removeAllElements() {
      size = 0;
    }

    //
    // Private methods
    //

    /**
     * Makes sure that there is enough storage.
     */
    private void ensureCapacity(int newsize) {

      if (data == null) {
        data = new int[newsize + 15];
      } else if (newsize > data.length) {
        int newdata[] = new int[newsize + 15];
        System.arraycopy(data, 0, newdata, 0, data.length);
        data = newdata;
      }

    } // ensureCapacity(int)

  } // class IntVector

} // class DeferredDocumentImpl
